package 图.最小生成树;

import 抽象数据类型.UF;
import 抽象数据类型.Edge;
import 抽象数据类型.EdgeWeightedGraph;
import 抽象数据类型.Queue;

import java.util.PriorityQueue;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-11
 */
public class 最小生成树的Kruskal算法 {
    public class KruskalMST {
        private final Queue<Edge> mst;
        private final PriorityQueue<Edge> pq;

        public KruskalMST(EdgeWeightedGraph g) {
            mst = new Queue<>();
            pq = new PriorityQueue<>((o1, o2) -> -o1.compareTo(o2));
            for (Edge e : g.edges()) {
                pq.offer(e);
            }
            UF uf = new UF(g.V());
            while (!pq.isEmpty() && mst.Size() < g.V() - 1) {
                Edge e = pq.poll();
                int v = e.either();
                int w = e.other(v);
                if (uf.connected(v, w)) {
                    continue;
                }
                uf.union(v, w);
                mst.enqueue(e);
            }

        }
        public Iterable<Edge> edges() {
            return mst;
        }

    }
}
